SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Constructible function</title>

</head>

Constructible function

</h1>

</header>

In <a href="Computational_complexity_theory" title="Computational complexity theory">complexity theory</a>, a time-constructible function is a function f from <a href="Natural_numbers" class="mw-redirect" title="Natural numbers">natural numbers</a> to natural numbers with the property that f(n) can be constructed from n by a <a href="Turing_machine" title="Turing machine">Turing machine</a> in the time of order f(n). The purpose of such a definition is to exclude functions that do not provide an upper bound on the runtime of some Turing machine.<a href="#cite_note-:0-1">[1]</a>

<div class="mw-heading mw-heading2"><h2 id="Time-constructible">Time-constructible</h2></div>

Let the Turing machine be defined in the standard way, with an alphabet that includes the symbols <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0,1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0,1}</annotation>

</semantics>

</math><img src="./a6d7ca945b5a3fb32ceb9513350b49ae0a19a4dc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.359ex; height:2.509ex;" alt="{\displaystyle 0,1}" loading="lazy">. It has a standard input tape containing zeros except for an input string. Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1^{n}}</annotation>

</semantics>

</math><img src="./00652fe252785bf869537e0795428eda58fe0b76.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.381ex; height:2.343ex;" alt="{\displaystyle 1^{n}}" loading="lazy"> denote a string composed of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> ones. That is, it's the <a href="Unary_numeral_system" title="Unary numeral system">unary representation</a>. Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |n|}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |n|}</annotation>

</semantics>

</math><img src="./35a62139afd28f74d3306e3bf603bebdecefe169.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.688ex; height:2.843ex;" alt="{\displaystyle |n|}" loading="lazy"> be the binary representation.

There are two different definitions of a time-constructible function.

In the first definition, a function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> is called time-constructible if there exists a Turing machine <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy">, such that for all but finitely many <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M(1^{n})}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M(1^{n})}</annotation>

</semantics>

</math><img src="./9ef923242c3ace91d5b89fce3ce30979273773bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.632ex; height:2.843ex;" alt="{\displaystyle M(1^{n})}" loading="lazy"> halts in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(f(n))}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(f(n))}</annotation>

</semantics>

</math><img src="./756b4d8648334719f65bf5e6269c7a2b3a502f13.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.065ex; height:2.843ex;" alt="{\displaystyle O(f(n))}" loading="lazy"> steps.

In the second definition, a function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> is called time-constructible if there exists a Turing machine <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy">, such that for all but finitely many <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M(1^{n})=|f(n)|}">

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M(1^{n})=|f(n)|}</annotation>

</semantics>

</math><img src="./80c92a29f6bc71918a9a3c416d092fbed9da361b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.507ex; height:2.843ex;" alt="{\displaystyle M(1^{n})=|f(n)|}" loading="lazy"> and halts in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(f(n))}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(f(n))}</annotation>

</semantics>

</math><img src="./756b4d8648334719f65bf5e6269c7a2b3a502f13.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.065ex; height:2.843ex;" alt="{\displaystyle O(f(n))}" loading="lazy"> steps.

The second definition may use <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M(1^{n})=1^{f(n)}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M(1^{n})=1^{f(n)}}</annotation>

</semantics>

</math><img src="./edb2c7416b55b83f3ec73102736f7ed52f9540bf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.295ex; height:3.343ex;" alt="{\displaystyle M(1^{n})=1^{f(n)}}" loading="lazy"> instead, since the two can be interconverted in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(f(n))}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(f(n))}</annotation>

</semantics>

</math><img src="./756b4d8648334719f65bf5e6269c7a2b3a502f13.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.065ex; height:2.843ex;" alt="{\displaystyle O(f(n))}" loading="lazy"> steps.<a href="#cite_note-:0-1">[1]</a>

<div class="mw-heading mw-heading3"><h3 id="Fully_time-constructable">Fully time-constructable</h3></div>

There is also a notion of a fully time-constructible function.

A function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> is called fully time-constructible if there exists a Turing machine <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy">, such that for all but finitely many <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M(1^{n})}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M(1^{n})}</annotation>

</semantics>

</math><img src="./9ef923242c3ace91d5b89fce3ce30979273773bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.632ex; height:2.843ex;" alt="{\displaystyle M(1^{n})}" loading="lazy"> halts in exactly <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(n)}</annotation>

</semantics>

</math><img src="./c1c49fad1eccc4e9af1e4f23f32efdc3ac4da973.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.483ex; height:2.843ex;" alt="{\displaystyle f(n)}" loading="lazy"> steps.<a href="#cite_note-:2-2">[2]</a> This definition is slightly less general than the first two but, for most applications, either definition can be used.<a href="#cite_note-:1-3">[3]</a> The following equivalence theorem shows that these two concepts are equivalent for most functions used in practice:

Theorem.<a href="#cite_note-:1-3">[3]</a>: Theorem 2.6 If <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> is a function such that there exists <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon >0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \epsilon >0}</annotation>

</semantics>

</math><img src="./568095ad3924314374a5ab68fae17343661f2a71.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.205ex; height:2.176ex;" alt="{\displaystyle \epsilon >0}" loading="lazy"> such that, for all but finitely many <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(n)\geq (1+\epsilon )n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(n)\geq (1+\epsilon )n}</annotation>

</semantics>

</math><img src="./24e9fb3e27dc94b9d49754a17c255985123486f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.732ex; height:2.843ex;" alt="{\displaystyle f(n)\geq (1+\epsilon )n}" loading="lazy">, then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> is time-constructible iff it is fully time-constructible.

More succinctly, the condition states that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(n)-n=\Omega (n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(n)-n=\Omega (n)}</annotation>

</semantics>

</math><img src="./7a2f7d0b7f280a49961569ac411750bd30724810.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.698ex; height:2.843ex;" alt="{\displaystyle f(n)-n=\Omega (n)}" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="Space-constructible">Space-constructible</h2></div>

Function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> is called space-constructible, if there exists a Turing machine <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy">, such that for all but finitely many <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M(1^{n})=|f(n)|}">

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M(1^{n})=|f(n)|}</annotation>

</semantics>

</math><img src="./80c92a29f6bc71918a9a3c416d092fbed9da361b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.507ex; height:2.843ex;" alt="{\displaystyle M(1^{n})=|f(n)|}" loading="lazy"> (or equivalently <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1^{f(n)}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1^{f(n)}}</annotation>

</semantics>

</math><img src="./30d0f154b34c4523b9c4e92ecefd9b848f1836d6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.564ex; height:2.843ex;" alt="{\displaystyle 1^{f(n)}}" loading="lazy">), while using <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(f(n))}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(f(n))}</annotation>

</semantics>

</math><img src="./756b4d8648334719f65bf5e6269c7a2b3a502f13.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.065ex; height:2.843ex;" alt="{\displaystyle O(f(n))}" loading="lazy"> space.<a href="#cite_note-:0-1">[1]</a>

Equivalently, if there exists a Turing machine <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy">, such that for all but finitely many <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> given <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1^{n}}</annotation>

</semantics>

</math><img src="./00652fe252785bf869537e0795428eda58fe0b76.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.381ex; height:2.343ex;" alt="{\displaystyle 1^{n}}" loading="lazy">, halts in a configuration in which exactly <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(n)}</annotation>

</semantics>

</math><img src="./c1c49fad1eccc4e9af1e4f23f32efdc3ac4da973.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.483ex; height:2.843ex;" alt="{\displaystyle f(n)}" loading="lazy"> cells are not blank, and no other cell has been written to during its operation.<a href="#cite_note-:1-3">[3]</a>: Definition 2.4 This is sometimes called "fully space-constructible". However, the two definitions are equivalent.<a href="#cite_note-:1-3">[3]</a>: Theorem 2.7

<div class="mw-heading mw-heading2"><h2 id="Properties">Properties</h2></div>

All the commonly used functions (such as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n,n^{2},2^{n},n!}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n,n^{2},2^{n},n!}</annotation>

</semantics>

</math><img src="./f533c6cbe4d6fdbfce39f17dcb41a4530620bfdf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.368ex; height:3.009ex;" alt="{\displaystyle n,n^{2},2^{n},n!}" loading="lazy">) are time- and space-constructible, as long as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(n)=\Omega (n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(n)=\Omega (n)}</annotation>

</semantics>

</math><img src="./2060e25d85609b16ffdcd49cc0548e77cd53fbdd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.463ex; height:2.843ex;" alt="{\displaystyle f(n)=\Omega (n)}" loading="lazy">. The construction is straightforward. For example, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n^{2}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n^{2}}</annotation>

</semantics>

</math><img src="./ac9810bbdafe4a6a8061338db0f74e25b7952620.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.449ex; height:2.676ex;" alt="{\displaystyle n^{2}}" loading="lazy"> is constructed by one for-loop, while <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n^{3}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n^{3}}</annotation>

</semantics>

</math><img src="./3e9d1a52e455a7a5272a345b2697e35f1579b681.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.449ex; height:2.676ex;" alt="{\displaystyle n^{3}}" loading="lazy"> is constructed by two for-loops, etc.

If <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(n)=o(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(n)=o(n)}</annotation>

</semantics>

</math><img src="./c8188b0a486bf27287cf6c8d15e8f5318c54b1ff.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.913ex; height:2.843ex;" alt="{\displaystyle f(n)=o(n)}" loading="lazy"> is time-constructible, then it is eventually constant, since otherwise there is insufficient time to read the entire input.

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ln n}</annotation>

</semantics>

</math><img src="./fc7e60afd0a48ba01cb2fee90f0199c28dce0298.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.721ex; height:2.176ex;" alt="{\displaystyle \ln n}" loading="lazy"> is space-constructible even though <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ln n=o(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ln n=o(n)}</annotation>

</semantics>

</math><img src="./b964fb0597d5b448b0be71ccd95dff5861f31039.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.151ex; height:2.843ex;" alt="{\displaystyle \ln n=o(n)}" loading="lazy">.

For every recursive function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy">, there is a recursive function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g}</annotation>

</semantics>

</math><img src="./d3556280e66fe2c0d0140df20935a6f057381d77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.116ex; height:2.009ex;" alt="{\displaystyle g}" loading="lazy"> which is time constructible and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \forall n,g(n)>f(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \forall n,g(n)>f(n)}</annotation>

</semantics>

</math><img src="./ac8a5c7efe29c79b78886887e24062e4b74829f6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.622ex; height:2.843ex;" alt="{\displaystyle \forall n,g(n)>f(n)}" loading="lazy">.<a href="#cite_note-:1-3">[3]</a>: Lemma 2.3

<div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2></div>

Time-constructible functions are used in results from complexity theory such as the <a href="Time_hierarchy_theorem" title="Time hierarchy theorem">time hierarchy theorem</a>. They are important because the time hierarchy theorem relies on Turing machines that must determine in <a href="Big-O_notation" class="mw-redirect" title="Big-O notation">O</a>(f(n)) time whether an algorithm has taken more than f(n) steps. This is, of course, impossible without being able to calculate f(n) in that time. Such results are typically true for all natural functions f but not necessarily true for artificially constructed f. To formulate them precisely, it is necessary to have a precise definition for a natural function f for which the theorem is true. Time-constructible functions are often used to provide such a definition.

Space-constructible functions are used similarly, for example in the <a href="Space_hierarchy_theorem" title="Space hierarchy theorem">space hierarchy theorem</a>.

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

This article incorporates material from constructible on <a href="PlanetMath" title="PlanetMath">PlanetMath</a>, which is licensed under the Creative Commons Attribution/Share-Alike License.

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFGoldreich2008" class="citation book cs1">Goldreich, Oded (2008). Computational Complexity: A Conceptual Perspective. Cambridge University Press. pp. 130, 139. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-521-88473-0</bdi>.</cite>

</li>

<li id="cite_note-:2-2"><a href="#cite_ref-:2_2-0">^</a> <cite id="CITEREFHomerSelman2011" class="citation book cs1">Homer, Steven; Selman, Alan L. (2011). Computability and Complexity Theory (Second ed.). Springer. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4614-0681-5</bdi>.</cite>

</li>

<li id="cite_note-:1-3">^ <a href="#cite_ref-:1_3-0">a</a> <a href="#cite_ref-:1_3-1">b</a> <a href="#cite_ref-:1_3-2">c</a> <a href="#cite_ref-:1_3-3">d</a> <a href="#cite_ref-:1_3-4">e</a> <cite id="CITEREFBalcázarDíazGabarró1988" class="citation book cs1">Balcázar, José Luis; Díaz, Josep; Gabarró, Joaquim (1988). Structural Complexity I. Springer-Verlag. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>3-540-18622-0</bdi>.</cite>

</li>

</ol></div></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-03-10" href="https://en.wikipedia.org/wiki/?title=Constructible_function&oldid=1279699786">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>